/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-09-19
 * Time: 22:17
 */
public class Test {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        int mid = left + (right - left) / 2;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid + 1,right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        //降序
        while(cur1 <= mid) {
            while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;
            if(cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }

        cur1 = left;
        cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++) nums[j] = tmp[j - left];

        return ret;
    }
}
